//Given an m x n matrix. If an element is 0, set its entire row and column to 0.
// Do it in-place. 
//
// Follow up: 
//
// 
// A straight forward solution using O(mn) space is probably a bad idea. 
// A simple improvement uses O(m + n) space, but still not the best solution. 
// Could you devise a constant space solution? 
// 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[1,1,1],
//                 [1,0,1],
//                 [1,1,1]]
//Output:         [[1,0,1],
//                [0,0,0],
//                [1,0,1]]
// 
//
// Example 2: 
//
// 
//Input: matrix = [[0,1,2,0],
//                 [3,4,5,2],
//                 [1,3,1,5]]

//Output:          [[0,0,0,0],
//                 [0,4,5,0],
//                 [0,3,1,0]]
// 
//
// 
// Constraints: 
//
// 
// m == matrix.length 
// n == matrix[0].length 
// 1 <= m, n <= 200 
// -231 <= matrix[i][j] <= 231 - 1 
// 
// Related Topics 数组 
// 👍 483 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Set Matrix Zeroes
class P73SetMatrixZeroes {
    public static void main(String[] args) {
        Solution solution = new P73SetMatrixZeroes().new Solution();
        // TO TEST
        solution.setZeroes(new int[][]{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void setZeroes(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            boolean flagCol0 = false, flagRow0 = false;
            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == 0) {
                    flagCol0 = true;
                }
            }
            for (int j = 0; j < n; j++) {
                if (matrix[0][j] == 0) {
                    flagRow0 = true;
                }
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        matrix[i][0] = matrix[0][j] = 0;
                    }
                }
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                        matrix[i][j] = 0;
                    }
                }
            }
            if (flagCol0) {
                for (int i = 0; i < m; i++) {
                    matrix[i][0] = 0;
                }
            }
            if (flagRow0) {
                for (int j = 0; j < n; j++) {
                    matrix[0][j] = 0;
                }
            }
        }

        public void setZeroes1(int[][] matrix) {
            HashMap<Integer, Integer> zeroMap = new HashMap<>();
            Set<Integer> rows = new HashSet<>();
            Set<Integer> cols = new HashSet<>();
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        int left = i, right = i;
                        if (!cols.contains(j)) {
                            while (left >= 0) {

                                zeroMap.put(left * matrix[0].length + j, 1);
                                left--;
                            }
                            while (right < matrix.length) {
                                zeroMap.put(right * matrix[0].length + j, 1);
                                right++;
                            }
                        }
                        left = j;
                        right = j;
                        if (!rows.contains(i)) {

                            while (left >= 0) {
                                zeroMap.put(i * matrix[0].length + left, 1);
                                left--;
                            }
                            while (right < matrix[0].length) {
                                zeroMap.put(i * matrix[0].length + right, 1);
                                right++;
                            }
                        }
                        rows.add(i);
                        cols.add(j);
                    }
                }
            }
            for (Integer integer : zeroMap.keySet()) {
                int i = integer / matrix[0].length;
                int j = integer % matrix[0].length;
                matrix[i][j] = 0;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}